\documentclass[UTF8]{ctexart}
\usepackage{xltxtra}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfigure}
%图片排版

\usepackage{listings,xcolor}
%代码块排版

\usepackage{booktabs}
%表格排版

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}  
%\usepackage{algorithm}  
%\usepackage{algorithmicx}  
%\usepackage{algpseudocode}  
\usepackage{amsmath}

\title{二叉树的区间搜索}
\author{陈乐瑶\\ 信息与计算科学\quad 3210103710}
\date{\today}
\begin{document}
\maketitle
\pagestyle{plain}
\lstset{numbers=left,
numberstyle=\tiny,
keywordstyle=\color{blue!70}, commentstyle=\color{red!50!green!50!blue!50},
frame=shadowbox,
rulesepcolor=\color{red!20!green!20!blue!20},
columns=flexible
}

\section{设计思路}
\textbf{目的：}输出给定二叉树中值在k1和k2之间的元素

一开始的想法是在main函数中利用外部函数进行迭代，从左往右搜索并中序输出。实现过程中发现不可避免地需要调用AvlTree类下的private根节点，因此最后选择将函数写在头文件中，避免指针调用出错。于是在AvlTree类的public下参考printTree（）的写法写了printKey(k1,k2)的接口,
在private下写printKey(t,k1,k2)的调用函数，核心算法如下：
\begin{lstlisting}[language={[ANSI]C++}]
    void printKey( AvlNode *t, Comparable k1, Comparable k2 ) const{
        if( t != nullptr ){
	  if ( t->element > k2 )
	    printKey( t->left, k1, k2 );
	  else if ( t->element >= k1 ){
	      printKey( t->left, k1, k2 );
	      cout << t->element <<'\t';
	      printKey( t->right, k1, k2 );
	    }
	  else
            printKey( t->right, k1, k2 );
        }
    }
\end{lstlisting} 

\section{理论分析}
\begin{enumerate}
\item 根据算法，首先从根节点开始搜索树中满足区间条件的最高子树根节点。假设该节点高度为h，对于N个元素的平衡树来说，树的高度为log2(N)，则这一步所需代价为log2(N)-h。
\item 其次，在以该节点为根的子树中寻找需要的元素。再次向左进行迭代直到找到满足t->element>=k1的最小元素，然后依次回溯（类似printTree的做法）中序输出（左子树中元素均小于根节点元素小于k2）。
\item 回到子树根节点后，对右子树进行同样的操作，判断t->element<=k2，若满足条件则依次输出该右子树的左子树（右子树中元素均大于根节点元素大于k1），后继续向右迭代搜索。这样的操作持续到t->element>k2时结束。
\item 假设树中满足在[k1,k2]之间条件的元素为K个，每次输出的代价为$\theta(1)$，则需要进行代价为$\theta(K)$的操作。而在2-3步的搜索过程中经历的步数和小于等于2h(h<log2(N))。
\end{enumerate}
因此我们推断，程序的运行时间为O(K+logN)。（可以通过数学归纳法加以验证）

\section{数值结果分析}
通过调用chrono库中的now()，利用运行时间反映复杂度。我们以一个简单的double平衡树为例：
\begin{lstlisting}[language={[ANSI]C++}]
  AvlTree<double> T;
  double k1, k2, N;
  std::cin>>N;//输入树的大小
  for( double i = 0; i < N; i++ )//建一个简单的AVLTree
    T.insert(i);
  std::cin>>k1;
  std::cin>>k2;
  auto begin_time = std::chrono::high_resolution_clock::now();
  T.printKey( k1, k2 );//运行程序
  auto end_time = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> elapsed = end_time - begin_time;
  std::cout<<"Running Time:"<<elapsed.count()<<"s\n"<<std::endl;
  //统计运行时间
\end{lstlisting}

\subsection{验证$T \propto K$}
取N=1000， k1=1，改变k2(K)的大小
\begin{table}[htbp]
  \caption{}
  \centering
  \begin{tabular}{ccccccccc}
    \toprule
    test &1 &2 &3 &4 &5 &6 &7 \\
    \midrule
    K &10 &20 &40 &80 &160 &320 &640 \\
    average time &4.372e-0.6 &8.615e-6 &1.7230e-5 &3.2707e-5 &6.5578e-4 &1.39341e-3 &2.39738e-3\\
    \bottomrule
  \end{tabular}
\end{table}

使用循环获取多组数据测试得到平均值后，绘制T—K图像并线性拟合，图像如下所示：
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.36\textwidth]{fig1.png}
  \caption{验证$T \propto K$}
\end{figure}

\subsection{验证$T \propto logN$}
取k1=1，k2=3（即K=3）,改变N的大小
\begin{table}[htbp]
  \caption{}
  \centering
  \begin{tabular}{ccccccccc}
    \toprule
    test &1 &2 &3 &4 &5 &6 &7 &8 \\
    \midrule
    N &$2^5$ &$2^{10}$ &$2^{15}$ &$2^{20}$ &$2^{22}$ &$2^{23}$ &$2^{24}$ &$2^{25}$ \\
    average time &1.357e-0.6 &1.441e-6 &1.594e-6 &1.8356e-6 &1.9385e-6 &2.0495e-6 &2.1597e-6 &2.2148e-6 \\
    \bottomrule
  \end{tabular}
\end{table}

使用循环获取多组数据测试(试了非常多非常多次终于得到与理论较吻合的数据)得到平均值后，绘制T—K图像并取对数后线性拟合，图像如下所示：
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.4\textwidth]{fig2.png}
  \includegraphics[width=0.4\textwidth]{fig3.png}
  \caption{验证$T \propto logN$}
\end{figure}


注意到，当K>>logN时，运行时间与K基本成正比，当logN>>K时，运行时间与logN基本成正比。而当两个变量相近或主变量小于次变量时，改变主变量的值并不能引起结果数据的线性变化;当我们同时改变两个变量时，结果数据故也并不以二次趋势增长（这些测试较多且杂这里未展示出来），故可以排除O(KlogN)这样的可能性。因此我们可以得到验证：该程序时间复杂度为O(K+logN)。

\section{内存泄漏测试}
\textbf{输入：}valgrind ./test

\textbf{输出：}
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.6\textwidth]{fig4.png}
  \caption{内存泄漏检查}
\end{figure}

\end{document}
